Java Software Structures [4th ed.]

Cover......Page 1
Preface......Page 8
Contents......Page 14
Credits......Page 26
Chapter 1: Introduction......Page 28
 1.1 Software Quality......Page 29
  Reliability......Page 30
  Usability......Page 31
  Reusability......Page 32
  Quality Issues......Page 33
  A Physical Example......Page 34
  Containers as Objects......Page 37
 Summary of Key Concepts......Page 38
Chapter 2: Analysis of Algorithms......Page 42
 2.1 Algorithm Efficiency......Page 43
 2.2 Growth Functions and Big-Oh Notation......Page 44
 2.3 Comparing Growth Functions......Page 46
  Nested Loops......Page 49
  Method Calls......Page 50
 Summary of Key Concepts......Page 53
Chapter 3: Introduction to Collections – Stacks......Page 56
 3.1 Collections......Page 57
  Abstract Data Types......Page 58
 3.2 A Stack Collection......Page 60
 3.3 Crucial OO Concepts......Page 62
  Inheritance and Polymorphism......Page 63
  Generics......Page 64
 3.4 Using Stacks: Evaluating Postfix Expressions......Page 65
  Javadoc......Page 72
 3.5 Exceptions......Page 73
 3.6 A Stack ADT......Page 75
 3.7 Implementing a Stack: With Arrays......Page 78
  Managing Capacity......Page 79
 3.8 The ArrayStack Class......Page 80
  The Constructors......Page 81
  The push Operation......Page 83
  The pop Operation......Page 84
  The EmptyCollectionException Class......Page 86
  Other Implementations......Page 87
 Summary of Key Concepts......Page 88
Chapter 4: Linked Structures – Stacks......Page 94
 4.1 References as Links......Page 95
  Accessing Elements......Page 97
  Inserting Nodes......Page 98
  Deleting Nodes......Page 99
  Doubly Linked Lists......Page 100
 4.4 Stacks in the Java API......Page 101
 4.5 Using Stacks: Traversing a Maze......Page 102
  The LinkedStack Class......Page 111
  The push Operation......Page 115
  The pop Operation......Page 117
  Other Operations......Page 118
 Summary of Key Concepts......Page 119
Chapter 5: Queues......Page 124
 5.1 A Conceptual Queue......Page 125
 5.2 Queues in the Java API......Page 126
 5.3 Using Queues: Code Keys......Page 127
 5.4 Using Queues: Ticket Counter Simulation......Page 131
 5.5 A Queue ADT......Page 136
 5.6 A Linked Implementation of a Queue......Page 138
  The enqueue Operation......Page 140
  The dequeue Operation......Page 142
  Other Operations......Page 143
 5.7 Implementing Queues: With Arrays......Page 144
  The enqueue Operation......Page 148
  The dequeue Operation......Page 150
 5.8 Double-Ended Queues (Deque)......Page 151
 Summary of Key Concepts......Page 152
Chapter 6: Lists......Page 156
 6.1 A List Collection......Page 157
 6.2 Lists in the Java Collections API......Page 159
 6.3 Using Unordered Lists: Program of Study......Page 160
 6.4 Using Indexed Lists: Josephus......Page 171
 6.5 A List ADT......Page 173
  Adding Elements to a List......Page 174
 6.6 Implementing Lists with Arrays......Page 179
  The remove Operation......Page 181
  The contains Operation......Page 183
  The add Operation for an Ordered List......Page 184
  The addAfter Operation for an Unordered List......Page 186
 6.7 Implementing Lists with Links......Page 187
  The remove Operation......Page 188
 Summary of Key Concepts......Page 190
Chapter 7: Iterators......Page 196
 7.1 What's an Iterator?......Page 197
 7.2 Using Iterators: Program of Study Revisited......Page 199
  Printing Certain Courses......Page 203
  Removing Courses......Page 204
 7.3 Implementing Iterators: With Arrays......Page 206
 7.4 Implementing Iterators: With Links......Page 208
 Summary of Key Concepts......Page 211
Chapter 8: Recursion......Page 214
  Infinite Recursion......Page 215
  Recursion in Math......Page 216
 8.2 Recursive Programming......Page 217
  Direct versus Indirect Recursion......Page 220
  Traversing a Maze......Page 221
  The Towers of Hanoi......Page 229
 8.4 Analyzing Recursive Algorithms......Page 234
 Summary of Key Concepts......Page 236
Chapter 9: Searching and Sorting......Page 242
 9.1 Searching......Page 243
  Generic Methods......Page 244
  Linear Search......Page 245
  Binary Search......Page 247
  Comparing Search Algorithms......Page 249
 9.2 Sorting......Page 250
  Selection Sort......Page 253
  Insertion Sort......Page 255
  Bubble Sort......Page 257
  Quick Sort......Page 259
  Merge Sort......Page 263
 9.3 Radix Sort......Page 266
 Summary of Key Concepts......Page 271
Chapter 10:Trees......Page 276
 10.1 Trees......Page 277
  Tree Classifications......Page 278
  Simulated Link Strategy for Array Implementation of Trees......Page 280
  Analysis of Trees......Page 282
  Preorder Traversal......Page 283
  Postorder Traversal......Page 284
  Level-Order Traversal......Page 285
 10.4 A Binary Tree ADT......Page 286
 10.5 Using Binary Trees: Expression Trees......Page 290
 10.6 A Back Pain Analyzer......Page 302
 10.7 Implementing Binary Trees with Links......Page 306
  The find Method......Page 311
  The iteratorInOrder Method......Page 313
 Summary of Key Concepts......Page 315
Chapter 11: Binary Search Trees......Page 320
 11.1 A Binary Search Tree......Page 321
 11.2 Implementing Binary Search Trees: With Links......Page 323
  The addElement Operation......Page 324
  The removeElement Operation......Page 327
  The removeAllOccurrences Operation......Page 330
  The removeMin Operation......Page 331
 11.3 Using Binary Search Trees: Implementing Ordered Lists......Page 333
  Analysis of the BinarySearchTreeList Implementation......Page 336
 11.4 Balanced Binary Search Trees......Page 337
  Right Rotation......Page 338
  Left Rotation......Page 339
  Leftright Rotation......Page 340
 11.5 Implementing BSTs: AVLTrees......Page 341
  Rightleft Rotation in an AVLTree......Page 342
 11.6 Implementing BSTs: Red/Black Trees......Page 344
  Insertion into a Red/Black Tree......Page 345
  Element Removal from a Red/Black Tree......Page 348
 Summary of Key Concepts......Page 351
Chapter 12: Heaps and Priority Queues......Page 358
 12.1 A Heap......Page 359
  The addElement Operation......Page 361
  The removeMin Operation......Page 362
 12.2 Using Heaps: Priority Queues......Page 363
 12.3 Implementing Heaps: With Links......Page 367
  The addElement Operation......Page 369
  The removeMin Operation......Page 371
 12.4 Implementing Heaps: With Arrays......Page 374
  The addElement Operation......Page 376
  The removeMin Operation......Page 377
 12.5 Using Heaps: Heap Sort......Page 379
 Summary of Key Concepts......Page 382
Chapter 13: Sets and Maps......Page 386
 13.2 Sets and Maps in the Java API......Page 387
 13.3 Using Sets: Domain Blocker......Page 390
 13.4 Using Maps: Product Sales......Page 393
 13.5 Using Maps: User Management......Page 397
 13.7 Implementing Sets and Maps Using Hashing......Page 402
 Summary of Key Concepts......Page 405
Chapter 14: Multi-Way Search Trees......Page 410
 14.2 2-3 Trees......Page 411
  Inserting Elements into a 2-3 Tree......Page 412
  Removing Elements from a 2-3 Tree......Page 414
 14.3 2-4 Trees......Page 417
 14.4 B-Trees......Page 419
  B+-Trees......Page 420
 14.5 Implementation Strategies for B-Trees......Page 421
 Summary of Key Concepts......Page 423
Chapter 15: Graphs......Page 428
 15.1 Undirected Graphs......Page 429
 15.2 Directed Graphs......Page 430
 15.3 Networks......Page 432
  Traversals......Page 433
  Testing for Connectivity......Page 437
  Minimum Spanning Trees......Page 439
 15.5 Strategies for Implementing Graphs......Page 442
  Adjacency Matrices......Page 443
 15.6 Implementing Undirected Graphs with an Adjacency Matrix......Page 444
  The addVertex Method......Page 449
  The expandCapacity Method......Page 450
 Summary of Key Concepts......Page 451
Appendix A: UML......Page 456
 UML Class Diagrams......Page 457
 UML Relationships......Page 459
 Summary of Key Concepts......Page 462
Appendix B: Object-Oriented Design......Page 464
 B.2 Using Objects......Page 465
  Abstraction......Page 466
  Creating Objects......Page 467
  The import Declaration......Page 469
 B.4 State and Behavior......Page 470
 B.5 Classes......Page 471
  Instance Data......Page 474
  Visibility Modifiers......Page 475
 B.7 Constructors......Page 477
 B.8 Method Overloading......Page 478
  The Null Reference......Page 479
  The this Reference......Page 480
  Aliases......Page 482
  Garbage Collection......Page 483
 B.10 The static Modifier......Page 484
  Static Methods......Page 485
 B.11 Wrapper Classes......Page 486
 B.12 Interfaces......Page 487
  The Comparable Interface......Page 488
  Derived Classes......Page 489
  The protected Modifier......Page 491
  Overriding Methods......Page 492
 B.14 Class Hierarchies......Page 493
  The Object Class......Page 494
  Abstract Classes......Page 495
 B.15 Polymorphism......Page 497
  References and Class Hierarchies......Page 498
  Polymorphism via Interfaces......Page 499
 B.16 Exceptions......Page 502
  The try Statement......Page 503
  Exception Propagation......Page 504
  The Exception Class Hierarchy......Page 505
 Summary of Key Concepts......Page 507
Appendix C: Java Graphics......Page 516
 C.1 Pixels and Coordinates......Page 517
 C.2 Representing Color......Page 518
 C.3 Drawing Shapes......Page 519
 C.4 Polygons and Polylines......Page 528
  The Polygon Class......Page 531
Appendix D: Graphical User Interfaces......Page 538
 D.1 GUI Elements......Page 539
  Frames and Panels......Page 540
  Buttons and Action Events......Page 544
  Determining Event Sources......Page 546
  Text Fields......Page 549
  Check Boxes......Page 552
  Radio Buttons......Page 556
  Sliders......Page 560
  Combo Boxes......Page 565
  Timers......Page 570
 D.3 Layout Managers......Page 575
  Flow Layout......Page 577
  Border Layout......Page 580
  Grid Layout......Page 584
  Box Layout......Page 587
  Mouse Events......Page 590
  Key Events......Page 599
  Extending Adapter Classes......Page 605
 D.5 Dialog Boxes......Page 606
  File Choosers......Page 609
  Color Choosers......Page 612
  Borders......Page 613
  Tool Tips and Mnemonics......Page 617
 D.7 GUI Design......Page 624
 Summary of Key Concepts......Page 625
Appendix E: Hashing......Page 634
 E.1 Hashing......Page 635
  The Division Method......Page 637
  The Mid-Square Method......Page 638
  The Length-Dependent Method......Page 639
  Chaining......Page 640
  Open Addressing......Page 643
  Deleting from a Chained Implementation......Page 647
  Deleting from an Open Addressing Implementation......Page 648
  The Hashtable Class......Page 649
  The HashMap Class......Page 651
  The IdentityHashMap Class......Page 652
  The WeakHashMap Class......Page 653
  LinkedHashSet and LinkedHashMap......Page 655
 Summary of Key Concepts......Page 657
Appendix F: Regular Expressions......Page 662
Index......Page 666